ОБ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ СХЕМАХ В БАЗИСЕ {х & y, х v y, ¬ х} ПРИ ИНВЕРСНЫХ НЕИСПРАВНОСТЯХ НА ВЫХОДАХ ЭЛЕМЕНТОВ 

Васин Алексей Валерьевич, аспирант Пензенского государственного университета, г. Пенза

718.95

Рассматривается задача синтеза асимптотически оптимальных схем, реализующих булевы функции, при инверсных неисправностях на выходах элементов в базисе {х & y, х v y, ¬ х}  . Доказано, что почти все булевы функции можно реализовать асимптотически оптимальными по надежности схемами, которые функционируют с ненадежностью, асимптотически равной 3ε при ε→0, где ε – вероятность инверсной неисправности на выходе базисного элемента. Сложность предлагаемых схем превышает сложность минимальных схем, построенных только из надежных элементов, не более чем в 3 раза.

 Скачать статью в формате PDF

1. Neuman von J. Probabilistic logics and the synthesis of reliable organisms from unreliable components / J. von Neuman // Automata studies / edited by C. Shannon, 
Mc. J. Carthy. – Princeton : Princeton University Press, 1956. – (Русский перевод: Автоматы. – М. : ИЛ, 1956. – С. 68–139).
2. Добрушин, Р. Л. О нижней оценке для избыточности самокорректирующихся схем из ненадежных функциональных элементов / Р. Л. Добрушин, С. И. Ортюков // Проблемы передачи информации. – 1977. – Т. 13. – № 1. – С. 82–89.
3. Добрушин, Р. Л. Верхняя оценка для избыточности самокорректирующихся схем из ненадежных функциональных элементов / Р. Л. Добрушин, С. И. Ортюков // Проблемы передачи информации. – 1977. – Т. 13. – № 3. – С. 56–76.
4. Ортюков, С. И. К вопросу о синтезе асимптотически безызбыточных самокорректирующихся схем из ненадежных функциональных элементов / С. И. Ортюков // Проблемы передачи информации. – 1977. – Т. 13. – № 4. – С. 3–8.
5. Ортюков, С. И. Метод синтеза асимптотически оптимальных самокорректирующихся схем, исправляющих близкую к линейной долю ошибок / С. И. Ортюков // Проблемы передачи информации. – 1981. – Т. 17. – Вып. 4. – С. 84–97.
6. Ортюков, С. И. Об избыточности реализации булевых функций схемами из ненадежных элементов / С. И. Ортюков // Труды семинара по дискретной математике и ее приложениям (Москва, 27–29 января 1987 г.). – М. : Изд-во Моск. ун-та, 1989. – С. 166–168.
7. Uhlig, D. Reliable networks from unreliable gates with almost minimal comlexity / D. Uhlig // Fundamentals of Computation Theory : Intern. сonf. FCT'87 (Kazan, June 1987). – Berlin : Springer-Verl., 1987. – P. 462–469. – (Lecture Notes in Comput. Sci.; V. 278). – (Русский перевод: Автоматы. – М. : ИЛ, 1956. – С. 68–139).
8. Редькин, Н. П. Надежность и диагностика схем / Н. П. Редькин. – М. : Изд-во МГУ, 1992.
9. Лупанов, О. Б. Асимптотические оценки сложности управляющих систем / О. Б. Лупанов. – М. : Изд-во МГУ, 1984.
10. Лупанов, О. Б. Об одном методе синтеза схем / О. Б. Лупанов // Известия вузов. Радиофизика. – 1958. – Т. 1. – № 1. – С. 120–140.
11. Pippenger, N. On networks of Noisy Gates / N. Pippenger // 26 Symposium on Foundation on Computer science (Portland, 21–23.10.1985). – Portland, 1985. – Р. 30–38.
12. Яблонский, С. В. Асимптотически наилучший метод синтеза надежных схем из ненадежных элементов / С. В. Яблонский // Banach Center. – 1982. – № 7. – P. 11–19.
13. Аксенов, С. И. О надежности схем над произвольной полной системой функций при инверсных неисправностях на выходах элементов / С. И. Аксенов // Известия высших учебных заведений. Поволжский регион. – 2005. – № 6 (21). – С. 42–55. – (Естественные науки).
14. Алехина, М. А. Синтез асимптотически оптимальных по надежности схем из ненадежных элементов : монография / М. А. Алехина. – Пенза : Информационно-издательский центр ПензГУ, 2006.
15. Чугунова, В. В. Синтез асимптотически оптимальных по надежности схем при инверсных неисправностях на входах элементов : дис. … канд. физико-математических наук / В. В. Чугунова. – Пенза, 2007.
16. Алехина, М. А. О сложности надежных схем при инверсных неисправностях на выходах элементов / М. А. Алехина, С. И. Аксенов // Дискретная математика и ее приложения : материалы IX Международного семинара, посвященного 75-летию со дня рождения академика О. Б. Лупанова (Москва, 18–23 июня 2007 г.). – М. : Изд-во мех.-мат. фак-та МГУ, 2007. – C. 56–59.